package tree;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * leet-code(211)  添加与搜索单词 - 数据结构设计
 * <p>
 * 题意与 208 题前缀树相似
 * <p>
 * 但是可以尝试新的算法
 *
 * @author Ringo
 * @date 2021/10/19 11:21
 */
public class WordDictionary {

    public static void main(String[] args) {
        WordDictionary wd = new WordDictionary();
        wd.addWord("abc");
        System.out.println(wd.search(".bc"));
        System.out.println(wd.search("abc"));
    }

    /**
     * key: 字符串长度
     * value: 字符串集合
     */
    private Map<Integer, Set<String>> map;

    public WordDictionary() {
        map = new HashMap<>(32);
    }

    /**
     * 添加字符串
     */
    public void addWord(String word) {
        int n = word == null ? 0 : word.length();
        Set<String> set = map.get(n);
        if (set != null) {
            set.add(word);
            return;
        }
        HashSet<String> val = new HashSet<>();
        val.add(word);
        map.put(n, val);
    }

    /**
     * 搜索字符串
     */
    public boolean search(String word) {
        int n = word == null ? 0 : word.length();
        Set<String> set = map.get(n);
        if (set == null || set.isEmpty()) {
            return false;
        }
        if (set.contains(word)) {
            return true;
        }

        // Java GOTO 语句
        P:
        for (String s : set) {
            for (int i = 0; i < n; ++i) {
                if (word.charAt(i) != '.' && word.charAt(i) != s.charAt(i)) {
                    continue P;
                }
            }
            return true;
        }
        return false;
    }
}
